/**
 * This is a sample implementation of a map structure where the keys and
 * values are stored naively in a linked list.
 * 
 * @param <K> the type of the keys
 * @param <V> the type of the values
 */

import java.util.Set;
import java.util.TreeSet;

public class MyLLMap<K, V> implements MyMap<K, V>
{
	
	private Node<Tuple> head;
	
	private class Tuple
	{
		private K key;
		private V val;
		public Tuple(K key, V val)
		{
			this.key = key;
			this.val = val;
		}
		public K getKey() { return key; }
		public V getVal() { return val; }
		public void setVal(V newVal) { val = newVal; }
	}
	
	public MyLLMap()
	{
		clear();
	}
	
	public void put(K key, V val)
	{
		// Search to update
		Node<Tuple> n = head;
		while (n != null)
		{
			if (key.equals(n.getData().getKey()))
			{
				n.getData().setVal(val);
				return;
			}
			n = n.getNext();
		}
		// Insert at front
		n = new Node<Tuple>(new Tuple(key, val), head);
		head = n;
	}
	
	public V get(K key)
	{
		Node<Tuple> n = head;
		while (n != null)
		{
			if (key.equals(n.getData().getKey()))
				return n.getData().getVal();
			n = n.getNext();
		}
		return null;
	}

	public boolean remove(K key)
	{
		// Can't do anything with empty list
		if (head == null)
			return false;
		// If removing head
		if (key.equals(head.getData().getKey()))
		{
			head = head.getNext();
			return true;
		}		
		// If removing anything else
		Node<Tuple> n = head.getNext(), prev = head;
		while (n != null)
		{
			if (key.equals(n.getData().getKey()))
			{
				prev.setNext(n.getNext());
				return true;
			}
			prev = n;
			n = n.getNext();
		}
		// Didn't find it
		return false;
	}

	public boolean contains(K key)
	{
		Node<Tuple> n = head;
		while (n != null)
		{
			if (key.equals(n.getData().getKey()))
				return true;
			n = n.getNext();
		}
		return false;
	}
	
	public void clear()
	{
		head = null;
	}

	public Set<K> keySet()
	{
		Set<K> keys = new TreeSet<K>();
		Node<Tuple> n = head;
		while (n != null)
		{
			keys.add(n.getData().getKey());
			n = n.getNext();
		}
		return keys;
	}
	
}
